iT邦幫忙

2024 iThome 鐵人賽

DAY 1
0
佛心分享-刷題不只是刷題

刷題小白與Python的動態規劃之旅系列 第 1

Day 01 引言、刷題實用Python語法整理

  • 分享至 

  • xImage
  •  

本文大綱

  • 引言
  • LeetCode 介紹
  • Python 複習
    • list(列表)與string(字串)的切片
    • generator 與 list comprehension
    • 刷題常用的模組
      • math
      • itertools
      • bisect
      • collections
      • heapq
      • functools

引言

大家好,我是半路出家、非本科系但最近開始學習程式語言當作興趣的夏。

去年此時,本著從做中學、一邊學習演算法一邊熟練Python語法的初衷,我開始每日一題Leetcode之旅,怎料越刷越覺得有趣,不知不覺半年過去後,持之以恆竟然也刷了數百題。

Leetcode軌跡

從一開始苦戰Medium難度,到逐漸能在Contest限時中解出一部分的Hard題,也逐漸對於「動態規劃」這個演算法中易學難精的大分類有一些心得。一直很憧憬鐵人賽的鐵人們,也從前幾屆的好文章中學到很多,剛好今年的題目有「佛心分享-刷題不只是刷題」這個主題,就決定參賽來拋磚引玉分享一下,希望能在書寫中再次梳理自己的概念,並幫助到和我一樣的初學者。

本系列文預計面向的讀者是像我一樣半路出家、沒有接觸過本科系演算法課程的初學者。如果沒有系統化的學過資料結構與演算法概念、直接上Leetcode刷題,可能Easy難度的題目能夠自力克服,但是一旦遇到暴力解無法突破、需要像是DP、DFS等等算法處理的問題時,即使有一個「能得到答案」的算法,卻未必是「時間、空間上足夠節省」的算法,就會TLE(超時)、MLE(記憶體空間不足)。

本系列文將會從動態規劃的基礎概念開始介紹,並從Easy到Hard由淺入深介紹Leetcode上各種適用動態規劃的題型,讓讀者也能掌握動態規劃的思維方式,將其舉一反三應用在題目上。

由於本文預計只會涉及動態規劃相關的概念與題型,如果和去年的我一樣完全是演算法小白,也推薦可以搭配這本帶我入門的白話演算法,內容涵蓋演算法與複雜度的基本概念,以及Binary Search、Quick Sort、DFS、BFS、Greedy...等其他刷題常見的算法。雖然這本書講的有點淺,但因為寫得很淺顯易懂,且範例都是簡單的Python語法,恰好適合新手入門。


LeetCode

LeetCode是目前很受歡迎的刷題練習平台,提供超過2000題不同難度的題目,涵蓋資料結構與演算法等領域。免費用戶就可以使用大多數的功能與大部分的題庫,練習題目或者參加競賽來學習或者準備面試。並且支持很多種語言,用戶可以使用自己習慣的語言來實作算法,也能參考其他人的答案。

本系列文會使用Leetcode上的題目作為範例,因此建議各位讀者註冊一個帳號,除了跟著本系列文介紹的題目練習,也可以挑戰每天的官方隨機考古題與每周末的競賽,讓學習效果更進一步!


Python 複習

本系列的所有文章,都會使用Python3語法作為範例,需要讀者熟悉Python的基本語法。

下文並不著重於介紹基礎語法,只會介紹幾個刷題時常用的Python語法糖與實用的函式庫。如果是完全的初學者,建議先參考網路上的常用語法教學,或者搭配Cheatsheet

list(列表)與string(字串)的切片

切片可以看成複製字串或者列表的一部分,但需要注意:對於嵌套列表來說,切片運算子是僅止於第一層的淺複製(Shallow Copy)

語法:直接在字串或者列表的名稱後面接中括號,規則是[開始:結束:間隔]

開始:包含。可以不寫(預設為0)

結束:不包含。可以不寫(預設為字串或者列表的長度)

間隔:可以不寫(預設為1)。如果寫2,代表每隔2個位置取一次值。如果為負值,代表反序取值。

例:

l = [0,1,2,3,4,5,6,7,8,9,10]

l[0:5:2] # [0,2,4]

l[9::-1] # [9,8,7,6,5,4,3,2,1,0]

generator 與 list comprehension

generator(生成器)可以想像成一台機器,根據我們設定的規則來把原料「加工」成產品

如果把產品接著放入一個list(列表),那麼這些產品就會成為list的內容,因此又叫做list comprehension(列表生成式)。

舉例而言,如果我們需要一個0~9的平方數的列表,可以這樣寫:

  1. 建立一個空列表
  2. 迭代0~9之間的所有整數,並且依序將這個整數平方,再放入列表
lst = []
for i in range(10):
    lst.append(i*i)

lst # [0, 1, 4, 9, 16, 25, 36, 49, 64, 81]

而利用列表生成式,也可以這樣寫:

lst = [ i*i for i in range(10) ]

lst # [0, 1, 4, 9, 16, 25, 36, 49, 64, 81]

列表生成式的寫法不僅行數較簡潔,也更容易讀出其內容。

列表生成式還能搭配判斷式使用,例如當我們要篩選一個列表中所有的偶數,可以像這樣寫:

nums = [1,2,3,4,5,6,7,8,9,10]

nums_even = [num for num in nums if num % 2 == 0]

當我們想根據簡單的規則生成列表,或者對列表內容進行簡單運算或者邏輯判斷時,列表生成式的寫法既好讀又好寫,推薦使用。

此外,生成式的寫法,不僅能用於生成list,也可以用來生成setdicttuple等容器資料型態,如下例:

d = {str(i)+'的平方':i*i for i in range(5)}

# {'0的平方': 0, '1的平方': 1, '2的平方': 4, '3的平方': 9, '4的平方': 16}

還可以直接作為參數,輸入「將list作為參數的函式」,例如summaxminmapreduce...等,如下例:

s = sum(i for i in range(1000) if i % 3 == 0 or i % 5 == 0)

# 233168 (0~999之中,被3或者5整除的整數的總和)

還可以用於建立巢狀式列表(矩陣),如下例:

sq = [[a*b for a in range(1,10)] for b in range(1,10)]

# 九九乘法表

在後續文章的例題中,我也經常會使用這種寫法來提升程式碼的可讀性。

延伸閱讀:Medium: 生成器與迭代器

刷題常用的模組

Python3的標準函式庫提供了許多實用的模組(module),在刷題時,有些重複使用到的功能並不是演算法與資料結構的學習重點,或者不是該題主要考的觀念,重複去寫很浪費時間。此時可以適當利用這些函式庫來加快學習的腳步。

當然,第一次寫到相關概念時,還是建議自己實作看看,確保自己瞭解背後的邏輯,畢竟面試時,仍可能要求你把這部分的虛擬碼或實際的程式碼一併寫出。

如果在LeetCode上面刷題,可以不需要import,直接call函式或類别的名稱,運行時也會自動去找標準函式庫裡面同名的函式或類別。

以下先列出幾個我刷題時經常引用的模組/函式。各函式實際的使用方式,在使用到的題目的文章中會再做說明:

math

就是數學公式的模組,例如math.sqrt(平方根)、math.pow(N次方)、math.perm(排列數)、math.comb(組合數)、math.ceil(向上取整)...等。

像是N次方、開根號之類的,背後也有提升計算效能的演算法,如果要完整的學習演算法時,建議也花時間去了解。

官方文檔:math

itertools

比較複雜的排列組合問題,當懶得自己寫一堆for去遍歷元素排列組合的時候可以用

官方文檔:itertools

bisect

二元搜尋法。最常用的是bisect.bisect_left,偶爾也會用到bisect.bisect_right

因為二元搜尋法寫起來很冗,所以像Contest這種要搶時間的情境,就可以偷懶一下。

二元搜尋法本身是經常考的題目,若讀者是為了面試而刷題練習的話,一定要自己熟悉實作之後才偷懶用函式庫。

官方文檔:bisect

collections

容器模組,因為基本庫只有listdictsettuple,這個庫裡面實作一些比較複雜的資料結構。

和二元搜尋法一樣,資料結構本身也是常考的題目,若讀者的學習重點、考題重點是在資料結構時,務必自己實作幾次,來熟悉它們背後的概念。

若像是「動態規劃搭配OO資料結構」這種題目時,適當的引用模組,可以讓程式碼更簡潔、可讀性更好,我們練習與複習時也能比較快掌握解法中的邏輯觀念。

刷題的經驗中我常用到以下幾個類:

collections.deque 雙端佇列(Double Ended QUEue)。就是頭、尾都可以取出、放入的queue

collections.Counter 計數器。想要對list內的元素出現頻率(次數)計數時使用,並內建一些方法,例如按照出現頻率排序、取其中出現次數最高的K個元素...等等

collections.defaultdict 預設值字典。Python基本庫的dict,如果我們直接索引一個不存在的key值是會直接噴Error的。defaultdict讓我們可以設定一個預設值,當你索引時,如果有這個key,就回傳對應的value,如果沒有這個key,就將這個keyvalue設定成預設值。

以上都是「實作並不麻煩,但是就有點冗」的資料結構。既然都挑Python來刷題了當然要讓自己刷得爽一點對吧(誤)

官方文檔:collections

heapq

實現一個heap queue(堆疊佇列)資料結構,來處理演算法中min heap或者max heap的需求。

主要用到的場合是一些Hard題,需要我們結合動態規劃與minheap來降低複雜度。

由於實作完整功能的heap真的要打很多行code,這個模組用起來就很爽。

官方文檔:heapq

functools

一些裝飾器(decorator)。

裝飾器是一種高階函式/類別的語法糖,高階函式/類別可以簡單理解為:以函式作為輸入與產出的函式/類別

在Python的語法糖中,只要在定義函式時,在def 的前一行寫@+裝飾器的名稱(裝飾子),就可以包裝你定義的函式。

本系列文會頻繁使用@cache這個「儲存函式已計算過的答案」的功能,來提高動態規劃Top-Down策略的程式碼的可讀性。(因為每題都要寫一模一樣的東西真的很冗)

語法寫起來像是這樣

@cache # 那我幫你把算過的答案計下來,有人問我就直接幫你回答,沒人問我再問你
def lazy_func(i): # 我很懶,只想計算我還沒算過的參數
    pass

在本系列前幾篇的文章中,會先手刻一次這個「儲存函式已計算過的答案」的部分,也會簡單解說@cache裝飾器的原理。

官方文檔:functools


以上為Day1的內容!感謝你的閱讀,如果有不同的想法或心得,歡迎留言一同討論!

本文也同步登載在我的個人部落格,記錄我的學習筆記與生活點滴,歡迎來逛逛。

明天會以費波那契數列為例,介紹動態規劃的基本觀念。


下一篇
Day 02 動態規劃簡介
系列文
刷題小白與Python的動態規劃之旅13
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言